#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

#     1
#    / \
#   2   2
#  / \ / \
# 3  4 4  3


# TODO: 也可以使用BFS 广度优先


class Solution:
    """
    @param root: root of the given tree
    @return: whether it is a mirror of itself
    """
    def isSymmetric(self, root):
        if not root:
            return True

        return self.is_symmetric(root.left, root.right)

    def is_symmetric(self, left, right):
        if (not left) and (not right):
            # 都为None
            return True

        if (not left) or (not right):
            # 只有一个为None
            return False

        if left.val != right.val:
            return False

        return self.is_symmetric(left.left, right.right) and self.is_symmetric(left.right, right.left)


def main():
    print("start main")

if __name__ == "__main__":
    main()
